|
In graph theory, a branch of combinatorial mathematics, a block graph or clique tree〔.〕 is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after Kôdi Husimi),〔 but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.〔See, e.g., , a 1983 review by Robert E. Jamison of another paper referring to block graphs as Husimi trees; Jamison attributes the mistake to an error in a book by Behzad and Chartrand.〕 Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.〔.〕 ==Characterization== Block graphs are exactly the graphs for which, for every four vertices ''u'', ''v'', ''x'', and ''y'', the largest two of the three distances ''d''(''u'',''v'') + ''d''(''x'',''y''), ''d''(''u'',''x'') + ''d''(''v'',''y''), and ''d''(''u'',''y'') + ''d''(''v'',''x'') are always equal.〔.〕〔.〕 They also have a forbidden graph characterization as the graphs that do not have the diamond graph or a cycle of four or more vertices as an induced subgraph; that is, they are the diamond-free chordal graphs.〔 They are also the Ptolemaic graphs (chordal distance-hereditary graphs) in which every two nodes at distance two from each other are connected by a unique shortest path,〔 and the chordal graphs in which every two maximal cliques have at most one vertex in common.〔 A graph ''G'' is a block graph if and only if the intersection of every two connected subsets of vertices of ''G'' is empty or connected. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs.〔.〕 Because of this property, in a connected block graph, every set of vertices has a unique minimal connected superset, its closure in the convex geometry. The connected block graphs are exactly the graphs in which there is a unique induced path connecting every pair of vertices.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Block graph」の詳細全文を読む スポンサード リンク
|